package com.leetcode.No0863;

import org.junit.Test;

import java.util.*;

/**
 * 	public class TreeNode {
 * 		int val;
 * 		TreeNode left;
 * 		TreeNode right;
 * 		TreeNode(int x) {
 * 			val = x;
 *      }
 * 	}
 *
 * @program: leetcode
 * @description: 二叉树中所有距离为 K 的结点
 * @author: wangzhihua
 * @date: 2021-07-30
 */
public class Solution01 {

	@Test
	public void test01() {
		TreeNode root = new TreeNode(0);
		root.left = new TreeNode(2);
		root.right = new TreeNode(1);
		root.right.left = new TreeNode(3);

		System.out.println(distanceK(root, root.right.left, 3));
	}

    private List<Integer> list = new ArrayList<Integer>();
    private boolean hasFindTargetFromRoot = false;
    private Deque<TreeNode> deque = new ArrayDeque<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        findKSon(target, k);
        // 当k==0时，后面会再运行一遍findKSon，会将target节点再次add进list中，所以这里直接return
        if (k == 0) {
        	return list;
        }
        // 记录从root到target的父节点之间经过的所有节点，不包括target，顺序同描述
	    findFatherChain(root, target);
	    if (deque.size() == 0) {
	    	return list;
	    }
        // 将target的父节点变为子节点
	    // 先清理target原有的子节点
	    target.left = null;
	    target.right = null;
	    // 将target的父节点变为其子节点，父节点的父节点变为父节点的子节点，以此类推
	    TreeNode preNode = target;
	    TreeNode nowNode = null;
	    int tmpK = k;
	    while (deque.size() > 0 && tmpK-- > 0) {
	    	nowNode = deque.pollLast();
	    	if (nowNode.left == preNode) {
	    		nowNode.left = null;
		    } else {
	    		nowNode.right = null;
		    }
	    	if (preNode.left == null) {
	    		preNode.left = nowNode;
		    } else {
	    		preNode.right = nowNode;
		    }
	    	preNode = nowNode;
	    }
	    findKSon(target, k);
	    return list;
    }

    public void findFatherChain(TreeNode node, TreeNode target) {
	    if (node == null || hasFindTargetFromRoot) {
		    return;
	    }
	    if (node == target) {
		    hasFindTargetFromRoot = true;
		    return;
	    }
	    deque.addLast(node);
	    findFatherChain(node.left, target);
	    findFatherChain(node.right, target);
        if (!hasFindTargetFromRoot) {
        	deque.pollLast();
        }
    }

    public void findKSon(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        if (k == 0) {
            list.add(node.val);
            return;
        }
        findKSon(node.left, k - 1);
        findKSon(node.right, k - 1);
    }

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) {
			val = x;
		}
	}

}
